package 左哥算法.ch10暴力递归;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Ch0从左往右的尝试模型 {
    /**
     * ch01求子集
     */
    @Test
    public void test01(){
        int[] nums={1,2,3};
        List<List<Integer>> subsets = subsets(nums,0,new LinkedList<>());
        subsets.forEach(o->System.out.println(o.toString()));
    }
    public List<List<Integer>> subsets(int[] nums) {
        return subsets(nums,0,new LinkedList<>());
    }

    /**
     * ch01求子集：给定一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。不能 包含重复的子集。
     *  思路：
     *      每个元素有两种选择，分别是要或不要。
     *      从左往右依次尝试要或不要
     */
    public List<List<Integer>> subsets(int[] nums,int curr,LinkedList<Integer> path) {
        List<List<Integer>> res=new LinkedList<>();
        if (curr>=nums.length){ //尝试完了
            List<Integer> copy = path.stream().collect(Collectors.toList());
            res.add(copy);
            return res;
        }
        res.addAll(subsets(nums,curr+1,path));
        path.add(nums[curr]);
        res.addAll(subsets(nums,curr+1,path));
        path.removeLast();
        return res;
    }

    /**
     * ch02:全排列问题（不包含重复）
     */
    @Test
    public void test02(){
        List<List<Integer>> permute = permute(new int[]{1,2,3}, 0);
        permute.forEach(System.out::println);
    }

    public List<List<Integer>> permute(int[] nums,int index) {
        List<List<Integer>> lists=new ArrayList<>();
        if (index==nums.length){
            List<Integer> collect = Arrays.stream(nums).boxed().collect(Collectors.toList());
            lists.add(collect);
            return lists;
        }
        for (int j = index; j < nums.length; j++) {
            swap(nums,j,index);
            lists.addAll(permute(nums,index+1));
            swap(nums,j,index);
        }
        return lists;
    }

    public void swap(int[] nums,int a,int b){
        int temp=nums[a];
        nums[a]=nums[b];
        nums[b]=temp;
    }
    /**
     * ch03组合问题
     */
    @Test
    public void test03(){
        combine(4,1,0,2,new int[2]);
        lists.forEach(System.out::println);
    }

    /**
     * 有n个数时，选k个出来，第index个位置选start后有多少种组合
     */
    List<List<Integer>> lists=new ArrayList<>();
    public void combine(int n,int start, int index,int k,int[] path) {
        if (k==0){
            lists.add(Arrays.stream(path).boxed().collect(Collectors.toList()));
            return;
        }
        while (start<=n-k+1){
            path[index]=start++;
            combine(n,start,index+1,k-1,path);
        }
    }

    public void combine2(int n,int index,int k,int[] path){
        if (k==0){
//            System.out.println(Arrays.toString(path));
            return;
        }
        if (index>n){
            return;
        }
        combine2(n,index+1,k,path);
        path[k-1]=index;
        combine2(n,index+1,k-1,path);
    }

    public void combine2(int n,int start, int index,int k,int[] path) {
        if (k==0){
//            System.out.println(Arrays.toString(path));
            return;
        }
        while (start<=n-k+1){
            path[index]=start++;
            combine2(n,start,index+1,k-1,path);
        }
    }

    @Test
    public void test(){
//        int count=100;
//        while (count-- > 0) {
//
//        }

        int k=5;
        long start = System.currentTimeMillis();
        combine2(100,1,0,k,new int[k]);
//        combine2(100,1,k,new int[k]);
        long end = System.currentTimeMillis();
        System.out.println(end-start);
        start=System.currentTimeMillis();
//        combine2(100,1,0,k,new int[k]);
        combine2(100,1,k,new int[k]);
        end=System.currentTimeMillis();
        System.out.println(end-start);
    }
}
